package 复习.面试TOP101.二叉树;


public class 重建二叉树 {
    int index = 0;
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin){
        return preorder(pre,vin,0,vin.length);
    }

    public TreeNode preorder(int[] pre,int[] vin,int left,int right){
        if(index == pre.length || left >= right) return null;
        int key = left;//找对应的下标
        while(key < right){
            if(pre[index] == vin[key]) break;
            key++;
        }
        TreeNode node = new TreeNode(pre[index]);
        node.left = preorder(pre,vin,left,key);
        node.right = preorder(pre,vin,key,right);
        return node;
    }
}

/*
public class Solution {
    int index = 0;
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin){
        return preorder(pre,vin,0,vin.length);
    }

    public TreeNode preorder(int[] pre,int[] vin,int left,int right){
        if(index == pre.length || right <= left) return null;
        int mid =  left;//准备遍历中序数组来找根节点
        while(mid < right){
            if(pre[index] == vin[mid]) break;
            mid++;
        }
        int val = pre[index++];
        TreeNode root = new TreeNode(val);
        root.left = preorder(pre,vin,left,mid);
        root.right = preorder(pre,vin,mid + 1,right);
        return root;
    }
}
 */
